A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets

摘要

This note is a stripped down version of a published paper on the Pottspartition function, where we concentrate solely on the linear coding aspect ofour approach. It is meant as a resource for people interested in coding theorybut who do not know much of the mathematics involved and how quantumcomputation may provide a speed up in the computation of a very importantquantity in coding theory. We provide a theorem on the quantum computation ofthe Weight Enumerator polynomial for a restricted family of cyclic codes. Thecomplexity of obtaining an exact evaluation is $O(k^{2s}(\log q)^{2})$, where$s$ is a parameter which determines the class of cyclic codes in question, $q$is the characteristic of the finite field over which the code is defined, and$k$ is the dimension of the code. We also provide an overview of cyclotomiccosets and discuss applications including how they can be used to speed up thecomputation of the weight enumerator polynomial (which is related to the Pottspartition function). We also give an algorithm which returns the coset leadersand the size of each coset from the list $\{0,1,2,...,N-1\}$, whose timecomplexity is soft-O(N). This algorithm uses standard techniques but we includeit as a resource for students. Note that cyclotomic cosets do not improve theasymptotic complexity of the computation of weight enumerators.